
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next() {}
};

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <cstddef>
#include <cstdlib> // 确保包含malloc所需的头文件
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        if(pHead==NULL||pHead->next==NULL)
            return pHead;
        
        ListNode* lesshead =(ListNode*)malloc(sizeof(ListNode));
        ListNode* lesstail=lesshead;
        ListNode* greaterhead =(ListNode*)malloc(sizeof(ListNode));
        ListNode* greatertail=greaterhead;
        
        while (pHead) 
        {
            if(pHead->val<x)
            {
                lesstail->next = pHead;
                lesstail = lesstail->next;
                
            }
            else
            {
                greatertail->next = pHead;
                greatertail = greatertail->next;
                
            }
            pHead = pHead->next;
        }
        greatertail->next = NULL;
        lesstail->next = greaterhead->next;
        ListNode* newhead = lesshead->next;
        free(lesshead);
        free(greaterhead);
        return newhead;
    }
};